package two.chapter_4.c4_1;

/**
 * 深度优先搜索连通分量
 */
public class DfsCC implements CC {
    private int id[];
    private boolean[] marked;
    private int count;
    public DfsCC(Graph g){
        id=new int[g.v()];
        marked=new boolean[g.v()];

        for (int s=0;s<g.v();s++){
            if (!marked[s]){
                dfs(g,s);
                count++;
            }
        }

    }

    private void dfs(Graph g, int v) {
        marked[v]=true;
        id[v]=count;
        for (int w:g.adj(v)){
            if (!marked[w]){
                dfs(g,w);
            }
        }
    }

    @Override
    public boolean connected(int v, int w) {
        return id[v]==id[w];
    }

    @Override
    public int count() {
        return count;
    }

    @Override
    public int id(int v) {
        return id[v];
    }
}
